package LeetCode75;

import publicClass.TreeNode;

/**
 * 1372. 二叉树中的最长交错路径
 * 给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
 *
 * 选择二叉树中 任意 节点和一个方向（左或者右）。
 * 如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
 * 改变前进方向：左变右或者右变左。
 * 重复第二步和第三步，直到你在树中无法继续移动。
 * 交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
 *
 * 请你返回给定树中最长 交错路径 的长度。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
 * 输出：3
 * 解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。
 * 示例 2：
 *
 *
 *
 * 输入：root = [1,1,1,null,1,null,null,1,1,null,1]
 * 输出：4
 * 解释：蓝色节点为树中最长交错路径（左 -> 右 -> 左 -> 右）。
 * 示例 3：
 *
 * 输入：root = [1]
 * 输出：0
 *
 *
 * 提示：
 *
 * 每棵树最多有 50000 个节点。
 * 每个节点的值在 [1, 100] 之间。
 */
public class T1372_二叉树中最长交错路径 {
    /**
     采用深度优先遍历的方式，我们可以从顶向下访问到所有节点。并且遍历下一个子节点时，我们也能够知道子节点是属于父节点的左子树，还是右子树。

     所以我们可以为每个节点缓存两个值，一个l表示到达当前节点时，该节点为左子树时的路径数，一个r表示该节点为右子树时的到达路径。
     当然，一个节点要么是左子树，要么是右子树，所以l和r其中只有一个有值。

     那么在遍历该节点的子节点时，如果子节点是左子树，那么它的l值就是父节点的r值加1. 如果是右子树，就是父节点的l值加1.

     作者：linxiaodong
     链接：https://leetcode.cn/problems/longest-zigzag-path-in-a-binary-tree/solution/dfsduan-duan-ba-xing-dai-ma-you-ya-jie-j-kfyz/
     来源：力扣（LeetCode）
     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    int maxLength = 0;
    public int longestZigZag(TreeNode root) {

        dfs(root,0,0);
        return maxLength;

    }

    void dfs(TreeNode root,int left,int right){

        if (root==null){
            return;
        }

        maxLength = Math.max(maxLength,left+right);

        dfs(root.left,right+1,0);
        dfs(root.right,0,left+1);


    }


}
